import java.util.ArrayList;

/**
 * 二分查找  數組必須有序
 */
public class Demo2 {
    public static void main(String[] args) {
        int[] arr = {1,5,10,34,34,34,231,444};
//        int index = binarySearch(arr,0,5,32);
//        System.out.println(index);

        ArrayList<Integer> arrayList = binarySearch2(arr,0,5,34);
        System.out.println(arrayList);
    }

    private static ArrayList binarySearch2(int[] arr,int left,int right,int findVal) {
        int mid = (left+right)/2;
        int midVal = arr[mid];
        //当查找的数据不存在时  会出现死递归
        //每次递归mid都会向前或向后移动一个位置 所以当left>right查询无果
        if(left>right){
            return null;
        }
        if(midVal>findVal){
             return  binarySearch2(arr,left,mid-1,findVal);
        }else if(midVal<findVal){
            return binarySearch2(arr, mid+1, right, findVal);
        }else{
            //找到findVal  扫描该位置左边或右边（数组有序）是否还存在要查找的值 创建一个list集合存储数据
            ArrayList<Integer> list = new ArrayList<>();
            list.add(mid);
            //往左扫描
            int temp = mid-1;
            while (true){
                //因为该数组有序，所以存在的与他相同的数  就在该位置附近
                if(temp<0 || arr[temp]!=findVal){
                    break;
                }
                list.add(temp);
                temp -= 1;
            }
            //往右扫描
            temp = mid+1;
            while (true){
                //因为该数组有序，所以存在的与他相同的数  就在该位置附近
                if(temp>arr.length-1 || arr[temp]!=findVal){
                    break;
                }
                list.add(temp);
                temp += 1;
            }
            return (ArrayList) list;
        }
    }

    /**
     *  不含有重复数据的数组
     * @param arr  数组
     * @param left 左边缩影
     * @param right  右边索引
     * @param findVal  查找的值
     * @return
     */
    private static int binarySearch(int[] arr,int left,int right,int findVal) {
        int mid = (left+right)/2;
        int midVal = arr[mid];
        //当查找的数据不存在时  会出现死递归
        //每次递归mid都会向前或向后移动一个位置 所以当left>right查询无果
        if(left>right){
            return -1;
        }
       if(midVal>findVal){
           return binarySearch(arr,left,mid-1,findVal);
        }else if(midVal<findVal){
           return binarySearch(arr, mid+1, right, findVal);
        }else {
           return mid;
        }
    }




}
